//
//  ProblemOffer21.swift
//  TestProject
//
//  Created by 武侠 on 2021/7/13.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 ✅
 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
 示例：
     输入：nums = [1,2,3,4]
     输出：[1,3,2,4]
     注：[3,1,2,4] 也是正确的答案之一。
 提示：
 0 <= nums.length <= 50000
 1 <= nums[i] <= 10000
 */
@objcMembers class ProblemOffer21: NSObject {
    func solution() {
//        print(exchangeT([1,2,3,4]))
        print(exchangex([2,16,3,5,13,1,16,1,12,18,11,8,11,11,5,1]))
    }
    
    func exchange(_ nums: [Int]) -> [Int] {
        var list = nums
        var l = 0, r = nums.count-1
        for i in 0..<nums.count {
            if nums[i] % 2 == 0 {
                list[r] = nums[i]
                r -= 1
            } else {
                list[l] = nums[i]
                l += 1
            }
        }
        
        return list
    }
    
    // l: 奇数
    // r: 偶数
    func exchangex(_ nums: [Int]) -> [Int] {
        var list = nums
        var l = 0, r = nums.count-1
        while l < r {
            while l < r, list[l] % 2 != 0 { //  找到左边第一个偶数的位置
                l += 1
            }
            
            while l < r, list[r] % 2 == 0 { //  走到右边第一个奇数的位置
                r -= 1
            }
            
            if r >= nums.count {
                break
            }
            
            // 交换：
            let t = list[l]
            list[l] = list[r]
            list[r] = t
        }
        
        return list
    }
    
    // fast指向的是奇数
    // slow指向的是偶数
    func exchangeT(_ nums: [Int]) -> [Int] {
        var list = nums
        var slow = 0, fast = 0
        while fast < list.count {
            while fast < list.count, list[fast] % 2 == 0 {  // 找到左边第一个奇数的位置
                fast += 1
            }
            if fast == list.count {
                break
            }
            
            // 交换：
            let t = list[fast]
            list[fast] = list[slow]
            list[slow] = t
            
            slow += 1
            fast += 1
        }
        
        return list
    }
    
   
}
